import java.util.ArrayList;
import java.util.PriorityQueue;
import java.util.Queue;
//topK问题
//给定一个长度为n的可能有重复值的数组，找出其中不去重的最小的k个数。例如数组元素是4,5,1,6,2,7,3,8这8个数字，则最小的4个数字是1,2,3,4(任意顺序皆可)。数据范围:0 <= k,n < =10000，
//数组中每个数的大小0 < =val <= 1000

//解法一：优先级队列默认是小根堆，直接全存入小根堆，然后取k个值即可
//时间复杂度：O(nlogn)  空间复杂度O(n)
public class Solution1 {
    public ArrayList<Integer> GetLeastNumbers_Solution (int[] input, int k) {
        Queue<Integer> queue = new PriorityQueue<Integer>();
        for (int num : input) {
            queue.offer(num);
        }
        ArrayList<Integer> list = new ArrayList<>();
        int count = k;
        while (count!=0) {
            list.add(queue.poll());
            count--;
        }
        return list;
    }
}

//解法二：如果当k远小于n时，如果使用维护大根堆的思路，那么可以将时间复杂度
//降低为O(nlogk)
//算法的核心思想是维护一个大小为 k 的大根堆。
//堆内始终存储当前最小的前 k 个元素，当有新元素比堆顶元素小时，
//将堆顶替换为新元素并重新调整堆,从而确保堆内始终是前k小的元素(因为题中不要求返回有序)
//时间复杂度O(nlogk) 空间复杂度O(n)
class Solution2{
    public ArrayList<Integer> GetLeastNumbers_Solution (int[] input, int k) {
        // 边界条件：如果 k 大于数组长度或 k 为 0，返回空列表
        if (k == 0 || input.length < k) {
            return new ArrayList<>();
        }
        // 创建一个大根堆（使用自定义 Comparator 实现）
        Queue<Integer> maxHeap = new PriorityQueue<>(k, (a, b) -> b - a);
        // 遍历数组，维护堆的大小为 k
        for (int num : input) {
            if (maxHeap.size() < k) {
                maxHeap.offer(num); // 堆未满时，直接加入
            } else if (num < maxHeap.peek()) {
                // 如果新元素比堆顶元素小，替换堆顶并调整堆
                maxHeap.poll();
                maxHeap.offer(num);
            }
        }
        // 将堆中的元素输出到结果列表
        return new ArrayList<>(maxHeap);
    }
}
